package lineartable.linkedlist.staticlinkedlist;

import lineartable.inter.LinearLinkedList;
import lineartable.inter.LinearList;

/**
 * 线性表链式存储结构-静态链表
 */
public class StaticLinkedList implements LinearLinkedList {
    // 数组长度
    private int length = 255;
    // 存储数据的数组
    private StaticLinkedNode[] arr;

    public StaticLinkedList() {
        arr = new StaticLinkedNode[length];
        // 将数组中的各分量链成备用链表
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new StaticLinkedNode();
            arr[i].setCur(i + 1);
        }
        // 最后一个节点记录链表的头节点，初始化为0
        arr[length - 1].setCur(0);
    }

    /**
     * 返回分配节点的下标
     *
     * @return
     */
    public int mollocSLL() {
        // 如果备用arr[0]指向的第一个元素是数组的最后一个元素，那么备用节点已经用完
        if (arr[0].getCur() == length - 1) {
            return -1;
        }
        // 获取到备用链表的第一个节点
        int rst = arr[0].getCur();
        // 将下一个节点的下标赋值给arr[0]
        arr[0].setCur(arr[rst].getCur());
        return rst;
    }

    /**
     * 回收节点到备用链表中
     *
     * @param index 要回收的节点的下标
     */
    public void freeSLL(int index) {
        if (index <= 0 || index >= length - 1) {
            return;
        }
        arr[index].setCur(arr[0].getCur());
        arr[0].setCur(index);
    }

    /**
     * 头插法建表
     *
     * @param data
     */
    @Override
    public void createListHead(char data) {
        int tempIndex = mollocSLL();
        arr[tempIndex].setData(data);
        arr[tempIndex].setCur(arr[length - 1].getCur());
        arr[length - 1].setCur(tempIndex);
    }

    /**
     * 尾插法建表
     *
     * @param data
     */
    @Override
    public void createListTail(char data) {
        int p = length - 1;
        while (arr[p].getCur() != 0) {
            p = arr[p].getCur();
        }
        int temp = mollocSLL();
        arr[temp].setData(data);
        arr[temp].setCur(0);
        arr[p].setCur(temp);
    }

    /**
     * 返回线性表是否为空
     *
     * @return
     */
    @Override
    public boolean listEmpty() {
        return arr[length - 1].getCur() == 0;
    }

    /**
     * 将线性表清空
     */
    @Override
    public void clearList() {
        arr = new StaticLinkedNode[length];
        // 将数组中的各分量链成备用链表
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new StaticLinkedNode();
            arr[i].setCur(i + 1);
        }
        // 最后一个节点记录链表的头节点，初始化为0
        arr[length - 1].setCur(0);
    }

    /**
     * 返回线性表中第i个位置元素
     *
     * @param index
     * @return
     */
    @Override
    public char getElem(int index) {
        int p = length - 1;
        for (int i = 0; i <= index; i++) {
            p = arr[p].getCur();
        }
        return arr[p].getData();
    }

    /**
     * 查找线性表中的元素，并返回下标(在链表中的位置，不是数组的下标)
     *
     * @param e
     * @return
     */
    @Override
    public int locateElem(char e) {
        int p = length - 1;
        int i = 0;
        while (arr[p].getCur() != 0) {
            p = arr[p].getCur();
            if (arr[p].getData() == e) {
                return i;
            }
            i++;
        }
        return -1;
    }

    /**
     * 在线性表第i个位置插入元素e
     *
     * @param i
     * @param e
     */
    @Override
    public void listInsert(int i, char e) {
        // 插入的位置小于0或者大于当前链表长度，则不执行任何操作
        if (i < 0 || i > getListLength()) {
            return;
        }
        // 获取到备用节点，把值放到备用节点中
        int j = this.mollocSLL();
        arr[j].setData(e);
        // 记录循环到的节点，指向链表的头节点
        int p = length - 1;
        // 让第i-1个节点的cur指向该节点
        for (int m = 0; m < i; m++) {
            p = arr[p].getCur();
        }
        // 新增节点指向i-1节点的下一个节点
        arr[j].setCur(arr[p].getCur());
        // i-1节点指向新增节点
        arr[p].setCur(j);
    }

    /**
     * 删除链表中的第i个元素
     *
     * @param i
     */
    @Override
    public void listDelete(int i) {
        int p = length - 1;
        for (int j = 0; j < i; j++) {
            p = arr[p].getCur();
        }
        // 记录要删除元素在数组中的下标
        int temp = arr[p].getCur();
        arr[p].setCur(arr[temp].getCur());
        // 回收空闲节点
        freeSLL(temp);
    }

    /**
     * 返回线性表中元素个数
     *
     * @return
     */
    @Override
    public int getListLength() {
        int p = length - 1;
        int i = 0;
        while (arr[p].getCur() != 0) {
            i++;
            p = arr[p].getCur();
        }
        return i;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        int p = length - 1;
        while (arr[p].getCur() != 0) {
            p = arr[p].getCur();
            stringBuilder.append(arr[p].getData() + ",");
        }
        // 如果数组中有元素才删除最后一个“，”符号
        if (stringBuilder.length() > 1) {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
